
#include <chrono>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

#include "common/functional_memoization.hpp"
#include "common/recursive_memoization.hpp"

int fib_common_recursion(int n)
{
    if (n == 0 || n == 1) {
        return n;
    }
    return fib_common_recursion(n - 2) + fib_common_recursion((n - 1));
}

int fib_tail_recursion(int n, int a = 0, int b = 1)
{
    if (n == 0) {
        return a;
    }
    if (n == 1) {
        return b;
    }
    return fib_tail_recursion(n - 1, b, a + b);
}

int fib_accumulate(int n)
{
    if (n == 0 || n == 1) {
        return n;
    }
    // std::vector<int> indices(n - 1, 0);
    // return std::accumulate(indices.cbegin(), indices.cend(), std::make_pair(0, 1),
    //     [](std::pair<int, int> acc, int) { return std::pair<int, int> { acc.second, acc.first + acc.second }; })
    //     .second;

    auto acc = std::pair<int, int> { 0, 1 };
    for (int i = 0; i < n - 1; ++i) {
        acc = { acc.second, acc.first + acc.second };
    }
    return acc.second;
}

std::vector<unsigned int> fib_cache_vector { 0, 1 };
unsigned int fib_cache(unsigned int n)
{
    if (fib_cache_vector.size() > n) {
        return fib_cache_vector[n];
    }
    const auto result = fib_cache(n - 2) + fib_cache(n - 1);
    fib_cache_vector.push_back(result);
    return result;
}

template <typename F>
unsigned int fib(F&& fibmemo, unsigned int n)
{
    std::cout << "fibmemo " << n - 1 << " and " << n - 2 << std::endl;
    return n == 0 ? 0
        : n == 1  ? 1
                  : fibmemo(n - 1) + fibmemo(n - 2);
}

int main()
{
    std::chrono::high_resolution_clock::time_point start, after;
    // std::cout << "fib(40): " << fib_common_recursion(40) << std::endl;
    // std::cout << "fib(40): " << fib_tail_recursion(40) << std::endl;
    // std::cout << "fib(15): " << fib_accumulate(15) << std::endl;
    /*
    auto fib_general_cached = functional_memoization(fib_common_recursion);

    std::cout << "---------------------------------------------" << std::endl;
    start = std::chrono::high_resolution_clock::now();
    std::cout << "fib(): " << fib_general_cached(40) << std::endl;
    after = std::chrono::high_resolution_clock::now();
    std::cout << "fib_general_cached() cost: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(after - start) << std::endl;
    std::cout << "---------------------------------------------" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::cout << "fib(): " << fib(fib_general_cached, 40) << std::endl;
    after = std::chrono::high_resolution_clock::now();
    std::cout << "unsigned int fib(F&& fibmemo, unsigned int n) cost: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(after - start) << std::endl;
    std::cout << "---------------------------------------------" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::cout << "fib(): " << fib_general_cached(40) << std::endl;
    after = std::chrono::high_resolution_clock::now();
    std::cout << "fib_general_cached() cost: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(after - start) << std::endl;
    std::cout << "---------------------------------------------" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::cout << "fib(): " << fib(fib_general_cached, 40) << std::endl;
    after = std::chrono::high_resolution_clock::now();
    std::cout << "unsigned int fib(F&& fibmemo, unsigned int n) cost: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(after - start) << std::endl;
    std::cout << "---------------------------------------------" << std::endl;
*/
    auto fibmemo = make_memoized_r<unsigned int(unsigned int)>(
        [](auto& fib, unsigned int n) {
            return n < 2 ? n : fib(n - 1) + fib(n - 2);
        });

    start = std::chrono::high_resolution_clock::now();
    std::cout << "fib(): " << fibmemo(40) << std::endl;
    after = std::chrono::high_resolution_clock::now();
    std::cout << "unsigned int fib(F&& fibmemo, unsigned int n) cost: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(after - start) << std::endl;
    std::cout << "---------------------------------------------" << std::endl;
    start = std::chrono::high_resolution_clock::now();
    std::cout << "fib(): " << fibmemo(40) << std::endl;
    after = std::chrono::high_resolution_clock::now();
    std::cout << "unsigned int fib(F&& fibmemo, unsigned int n) cost: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(after - start) << std::endl;
    std::cout << "---------------------------------------------" << std::endl;

    return 0;
}